1. Field of the Invention
The present invention relates generally to a resource allocation method for providing load balancing and fairness for a dual ring, and more particularly to a resource allocation method for providing load balancing and fairness for a dual ring, which is capable of increasing the efficiency of utilization of resources by balancing loads on the dual ring including a plurality of nodes, and which is capable of providing fairness to the nodes as well as increasing the efficiency of utilization of resources by controlling the traffic of a best effort service in consideration of ring topology.
2. Description of the Prior Art
A dual ring scheme, as depicted in FIG. 1, is a communication method in which a plurality of nodes N0˜N4 communicate with each other while sharing two rings 11 and 12 that transmit data in opposite directions, which is adopted in Resilient Packet Ring (RPR) networks, Synchronous Optical NETworks (SONETs), Fiber Distributed Data Interface (FDDI) networks, token ring networks, or the like.
Meanwhile, in the conventional FDDI or token ring networks, once even unicast data transmitted between a single transmitter and a single receiver is transmitted to a ring, the unicast data cannot be eliminated at a receiving node, but is eliminated only at a transmitting node, so the efficiency of the ring is relatively low. The SONET is disadvantageous in that only one of its two rings is used to transmit data and multicast or broadcast data should be transmitted to each of receiving nodes.
In order to overcome the above-described problems, Dynamic synchronous Transfer Mode (DTM) and Dynamic Packet Transfer (DPT) remove unicast data, transmitted by a transmitting node, from a receiving node to be reused by other nodes. This is referred to as spatial reuse, which allows ring resources to be efficiently used.
In addition, the resource allocation methods that take loads into consideration include a method in which a server or Quality of Service (QoS) broker is provided at a center and the server or QoS broker allocates resources in consideration of the traffic of all networks, a method in which resources are allocated to next nodes one by one, and a method in which K possible paths are previously detected and resources are allocated to the paths.
These conventional resource allocation methods require complicated processes and an excessive amount of information so as to take the loads of a network into consideration. In a dual ring, two paths exist between a source and a destination, so it is easy for every node of the dual ring to manage ring resource allocation information. Accordingly, these conventional resource allocation methods are not inappropriate to the dual ring.
In the meantime, to solve the disadvantages of the above-described conventional resource allocation methods, there have been proposed a plurality of schemes, some of which are described below.
U.S. Pat. No. 6,363,319 issued on Mar. 26, 2002 and entitled “Constant-based Route Selection Using Biased Cost” had proposed the introduction of biased cost parameters to overcome a load concentration phenomenon that is a problem of a conventional routing method in which a shortest path is selected at the time of allocating a path. In this case, the flow attribute includes a flow priority and a bandwidth demand, and the path attribute includes a link bandwidth and a maximum available link bandwidth. Traffic efficiency can be increased by taking into consideration the flow priority, the bandwidth demand, the link bandwidth and the maximum available link bandwidth in route selection.
In this patented method, route selection can be performed in both a central manner in which a central network server performs the route selection and a distributed manner in which each of label edge routers performs the route selection. In the case where the central server selects a route, excessive time and resources are required for the central server to calculate the paths. In the case of the distributed type method, the available bandwidths of all nodes are periodically advertised, biased costs are calculated and a path having a lowest biased cost is selected. Accordingly, as the period for which the available bandwidths are advertised becomes shorter, information becomes more apparent but overhead becomes larger; while as the period for which the available bandwidths are advertised becomes longer, overhead becomes smaller but information becomes scarcer.
U.S. Pat. No. 6,108,338 entitled “Method and Device for Dynamic Synchronous Transfer Mode in a Dual Ring Topology” proposed a method and device for transmitting packets on a dual ring in Dynamic Synchronous Transfer Mode (DTM). This patented method is intended to solve the problem in which in a token ring or Fiber Distributed Data Interface (FDDI) using shared mediums, a packet is deleted at a transmitting node having transmitted a packet, so only a single node can transmit a packet at one time. In this patented method, necessary time slots are allocated and data is transmitted according to allocated time slots. These time slots consist of control slots and data slots. This method works in such a way that the controller of each node additionally requests necessary data slots through a control slot in the case of an increase in the traffic of the node and data are transmitted through allocated data slots in the case of the allocation of data slots from one of other nodes. That is, necessary resources are dynamically allocated depending on traffic.
This patented method is advantageous in that a data slot can be reused because unicast data is deleted from a receiving node, and latency and packet loss, that is, defects of a packet-switched network, can be reduced and low link efficiency, that is, a defect of a circuit-switched network, can be improved because data are transmitted according to allocated time slots.
However, this patented method is disadvantageous in that necessary time slots are requested, allocated and used in the case of an increase in traffic, and one of other nodes cannot use one or more of the allocated time slots even in the case of not transmitting data using the time slots, thus wasting resources.
Another method is a method in which best effort data is first transmitted in the case of the existence of the best effort data to be transmitted on a dual ring and a rate is reduced in the case of congestion. Examples of this method include a method and distributed bandwidth allocation for spatial and local reuse disclosed in U.S. Pat. No. 6,314,110, a fairness algorithm for high-speed networks based on a Resilient Packet Ring (RPR) architecture (Stein Gjessing, CAC' 02, 2002), Distributed Virtual-time Scheduling in rings (DVSR, V. Gambiroza, et Al., Rice Univ., U.S.), High Performance Fair Bandwidth Allocation for Resilient Packet Rings (Proc. 15th ITC specialist seminar on traffic engineering and traffic management), etc.
In that case, the pair algorithms of the SRP and the RPR basically use similar control mechanisms. That is, each node belonging to a ring is comprised of an input buffer, an output buffer and a transmission buffer. Each of these buffers is operated in a first-in, first-out manner and undergoes a priority service. The priority of the priority service may include high, medium and low priority. Only negotiated traffic is received under high priority, and the received traffic undergoes a high priority service. A negotiated bandwidth undergoes a medium priority service, while a bandwidth exceeding the negotiated bandwidth undergoes a low priority service. Low priority traffic is provided with high utilization and fairness by a fairness algorithm.
These methods are controlled through four principal parameters, that is, an local_fair_rate, an advertised rate advertised_rate, an allowed rate allow_rate and a forward rate forward_rate. Each node periodically generates a fair packet. The node transmits null information to an upstream node in the case of no congestion and its local_fair_rate to the upstream node in the case of congestion, which rate is referred to as an advertised rate. When congestion occurs at a downstream node and a base node receives an advertised rate, the received advertised rate is set to the local fair rate, the own rate of the base node is reduced to be equal to or lower than the allowed rate and the advertised rate is transmitted to an upstream node. When congestion occurs at the base node, the base node sets a lower one of its local fair rate and received rate to an advertised rate and transmits the advertised rate to the upstream node. When congestion is eliminated by the upstream nodes reducing their rates, the rate of the congested node is gradually increased and this increased rate becomes an advertised rate, so the rates of other nodes are similarly increased and therefore all the nodes are stabilized. In the case where rates are increased by the elimination of congestion, when the rate of a link is C, a reserved rate is rev_rate and the increase coefficient of an allowed rate is Growth_coeff, an allowed rate calculated at regular periods is calculated using the following equation.
                                                        allowed_rate              =                            ⁢                              allowed_rate                +                                                                            C_rev                      ⁢                      _rate                                        -                    allowed_rate                                    Growth_coeff                                                                                                                      ⁢                              if                ⁢                                                                  ⁢                advertised_rate                ⁢                                                                  ⁢                is                ⁢                                                                  ⁢                null                                                                                        =                            ⁢                                                                    allowed_rate                    +                    advertised_rate                                    2                                +                                                                                                      ⁢                                                                    C                    -                    rev_rate                    -                    allowed_rate                                    Growth_coeff                                ⁢                                                                  ⁢                el                ⁢                                                                  ⁢                se                                                                        (        1        )            
In this method, the rate of a downstream node becomes an advertised rate at the time of congestion, and upstream nodes gradually reduce their own rates and increase them in stages.
In this case, if the own rate of each upstream node is excessively slowly or much reduced, there occurs a problem in which the efficiency of utilization of a ring is reduced. That is, if the own rate is rendered excessively slow at the time of congestion, the congestion continues and buffer overflow may occur. On the contrary, if the own rate is rapidly reduced to an advertised rate, congestion can be rapidly eliminated but link efficiency is reduced.
For example, if the traffic of an upstream node is C and the traffic of a downstream node is ε at a ring having a maximum capacity C, all the traffic of the downstream node is C+ε>C, thus causing congestion. When the congestion occurs, the downstream node informs the upstream node of its own rate ε, and the upstream node reduces its own rate to a value ε and gradually increases its own rate to the vicinity of a value C. When the rate of the upstream node is equal to or greater than C−ε, congestion occurs at the downstream node. In this case, the upstream node reduces its own rate to a value ε, so the minimum utilization of a link is 2ε. However, these methods are disadvantageous in that link efficiency is deteriorated by the periodic repetition of this process.
In order to solve the above-described disadvantages, DSVR is designed to increase the efficiency of utilization of resources and provide the fairness of nodes by measuring the number of active nodes and the rates of the active nodes, calculating a fair rate F of each node, transmitting the calculated fair rate to an upstream node and controlling the own rate of the upstream node according to the calculated fair rate at the upstream node.
This method generally increases the efficiency of utilization of rings and provides fairness to nodes, but reduces the efficiency of utilization of resources in the case where input traffic is dynamically and rapidly changed or traffic control is delayed between the transmitting node and the receiving node. Additionally, a receiving node must measure the traffic of all transmitting nodes that transmit data to the receiving node, so the method is disadvantageous in that hardware for implementing this method is complicated and it is difficult to calculate a fair rate for each of the nodes.